using System;
using System.Collections.Generic;
using System.Data.Linq;
using System.Text;

namespace GraphSpace
{
	class uniSearch<PQ> where PQ : IPQ, new()
	{
		PQ PriorityStuct = new PQ ();

		public int getDeleteMin ()
		{
			return PriorityStuct.getDeleteMinCounter ();
		}
		
        public uniSearch(int C)
        {
            PriorityStuct.init(C);
        }
        public uniSearch ()
        {

        }
		

        public double DoSearch (Graph G, Knoten initialKnoten, Knoten endKnoten, out Knoten[] Path, bool GoalDirected)
        {
        	//double AbstandST = Math.Abs (initialKnoten.x - endKnoten.x) + Math.Abs (initialKnoten.y - endKnoten.y);
        	initialKnoten.distance = 0;
        	initialKnoten.realdist = 0;
        	initialKnoten.besucht = true;
        	PriorityStuct.insert (initialKnoten);
        	//	try {
        	while (!PriorityStuct.isEmpty ()) 
			{
        		Knoten aktKnoten = PriorityStuct.extractHead ();
        		if (aktKnoten.id == endKnoten.id)
        			break;
    
				for (int i = 0; i < G.A[aktKnoten.id].Count; i++) 
				{
        			Knoten ZielKnoten = (Knoten)G.A[aktKnoten.id][i].Vnach;
        			//Unterschied zwischen normal oder zielgerichtet
        			if (GoalDirected) 
					{
        				int AbstandX = Math.Abs (endKnoten.x - ZielKnoten.x);
        				int AbstandY = Math.Abs (endKnoten.y - ZielKnoten.y);
        				double d = aktKnoten.realdist + G.A[aktKnoten.id][i].Gewicht;
        				double d_strich = d + AbstandX + AbstandY;
      
        				//	Console.WriteLine("Zielknoten "+ ZielKnoten.id + " akt "+ZielKnoten.distance + " neu "+NewDist);
        				if (!ZielKnoten.entfernt && d < ZielKnoten.realdist)
						{
        					ZielKnoten.predeseccor = aktKnoten;
        					ZielKnoten.realdist = d;
       
							if (!ZielKnoten.besucht) 
							{
        						//	Console.WriteLine(ZielKnoten.id + " neu eingefügt");
        						ZielKnoten.distance = d_strich;
        						ZielKnoten.besucht = true;
        						PriorityStuct.insert (ZielKnoten);
        					}
							else
							{
        						//			Console.WriteLine(ZielKnoten.id + " verbessert");
        						PriorityStuct.decreaseKey (ZielKnoten, d_strich);
        					}
        				}
        			} 
					else 
					{
        				double NewDist = aktKnoten.distance + (int)G.A[aktKnoten.id][i].Gewicht;
        				//Console.WriteLine("Zielknoten "+ ZielKnoten.id + " akt "+ZielKnoten.distance + " neu "+NewDist);
        				if (NewDist < G.A[aktKnoten.id][i].Vnach.distance) 
						{
        					ZielKnoten.predeseccor = aktKnoten;
        					ZielKnoten.distance = NewDist;
        					if (!ZielKnoten.besucht) 
							{
        						//		Console.WriteLine(ZielKnoten.id + " neu eingefügt");
        						ZielKnoten.besucht = true;
        						PriorityStuct.insert (ZielKnoten);
        					}
							else
							{
        						//Console.WriteLine(ZielKnoten.id + " verbessert");
        						PriorityStuct.decreaseKey (ZielKnoten, NewDist);
        					}
        				}
        			}
        		}
				aktKnoten.entfernt = true;
			}
				
			Knoten pred = endKnoten;
			List<Knoten> path = new List<Knoten> ();
			while (pred != null) 
			{
				path.Add (pred);
				pred = pred.predeseccor;
			}
					
			path.Reverse ();
			Path = path.ToArray ();
			if(GoalDirected)
				return endKnoten.realdist;
			else
				return endKnoten.distance;
		//	} 
//			catch (Exception e) 
//			{
//				Console.WriteLine ("uniSearch::DoSearch : " + e.Message);	
//			}
			//Path = new Knoten[0];
			return 0.0;
		}
	}
}

